from typing import *
from bisect import bisect_left, bisect_right


class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        a, b, c, d, m = nums1[0], nums1[-1], nums2[0], nums2[-1], len(nums2)
        mn, mx = min(a * c, a * d, b * c, b * d), max(a * c, a * d, b * c, b * d)
        l, r = mn, mx
        cnt = Counter(nums2)
        while l < r:
            md = ((r - l) >> 1) + l
            cmn, ceq = 0, 0
            for i, v in enumerate(nums1):
                if v == 0:
                    cmn += m if md > 0 else 0  # m个乘积都是0，纯小于md
                    ceq += m if md == 0 else 0  # m个乘积都是0，纯等于md
                else:
                    if v > 0:
                        fv = (md + v - 1) // v
                        p = bisect_left(nums2, fv)  # 乘积纯小于
                        cmn += p
                        if p < m and nums2[p] * v == md:  # 边界是不是乘积等于
                            ceq += cnt[nums2[p]]
                    else:
                        fv = md // v
                        p = bisect_right(nums2, fv)  # 乘积大于等于
                        cmn += m - p  # 剩下的是乘积纯小于
                        if p - 1 >= 0 and nums2[p - 1] * v == md:  # 边界是不是乘积等于
                            ceq += cnt[nums2[p - 1]]
            if cmn >= k:  # 纯小于里面有答案，猜大了，缩右界
                r = md - 1
            elif cmn + ceq >= k:  # 可能是这个
                r = md  # 用r收集答案
            else:
                l = md + 1  # 猜小了扩一下，从l撞r，
        return r


s = Solution()
print(
    s.kthSmallestProduct(
        nums1=[-3, -1, 5, 6], nums2=[-10, -7, -6, -5, -5, -4, -1, 7, 8], k=28
    )
)
print(s.kthSmallestProduct(nums1=[2, 5], nums2=[3, 4], k=2))
print(s.kthSmallestProduct(nums1=[-2, -1, 0, 1, 2], nums2=[-3, -1, 2, 4, 5], k=3))
